package com.Oct_Four;

/**
 * 1079. 活字印刷
 * 你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
 *
 * 注意：本题中，每个活字字模只能使用一次。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/letter-tile-possibilities
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/04 16:32
 */

public class Solution1079 {

    /**
     * 经典回溯写法，但是复杂度太高了，建议更改写法
     *
     * 2022/10/04 16:25
     */
//    Set<String> set;
//    boolean[] used;
//    public int numTilePossibilities(String tiles) {
//        used=new boolean[tiles.length()];
//        Arrays.fill(used,false);
//        set=new HashSet<>();
//        backTracking(tiles,new StringBuilder());
//        //System.out.println(set);
//        return set.size()-1;
//    }
//
//    public void backTracking(String s,StringBuilder sb){
//        //list.add(new ArrayList<List<String>>(sb));
//        set.add(sb.toString());
//        boolean[] words=new boolean[26];
//        for (int i=0;i<s.length();i++) {
//            //if (i>0&&s.charAt(i)==s.charAt(i-1)&&!used[i-1]) continue;
//            int index = s.charAt(i) - 'A';
//            if (!used[i] &&!words[index]) {
//                used[i] = true;
//                //words[index]=true;
//                backTracking(s, sb.append(s.charAt(i)));
//                used[i] = false;
//                words[index]=true;
//            }
//        }
//    }

    public static void main(String[] args) {
        Solution1079 solution1079=new Solution1079();
        System.out.println(solution1079.numTilePossibilities("AAABBC"));
    }

    int ans;

    public int numTilePossibilities(String tiles) {
        ans=0;
        int[] map=new int[26];
        for (int i=0;i<tiles.length();i++)
        {
            map[tiles.charAt(i)-'A']++;
        }
        dfs(map,tiles);
        return ans;
    }

    void dfs(int[] map,String s){
        for (int i=0;i<26;i++)
        {
            if (map[i]>0)
            {
                map[i]--;
                ans++;
                dfs(map,s);
                map[i]++;
            }
        }
    }

}
